【算法编程】随机数的不重复选择

​ 前一篇文章中，我们在Java中用实现两种不同接口的类，解决了不重复选择随机数的问题。现在我们在C++中，通过几种不同的算法来解决上述问题。在下面的四种算法实现中，用的随机函数都是C的库函数，这个函数产生的随机数的范围是限定的，[0, 32767]。当然我们可以通过四则运算来改变取值范围。具体的算法实现如下：

#include<iostream>
#include<ctime>
#include<algorithm>
#include <set>
using namespace std;

/****************************************\
函数功能：从n个数中随机选择m个不同的数
函数输入：n为样本空间，m为选择的个数
函数输出：在屏幕上打印选取的数
算法描述：结果范围在[0,n),呈递增数列，
          当n比较大m比较小时，耗时较大
\****************************************/
void random1(int n,int m)
{
	srand(time(NULL));//使用这个就可以每次运行不同
	for(int i=0;i<n;i++)
	{
		if(rand()%(n-i)<m)
		{
			cout<<i<<endl;//随机数结果按递增顺序排列
			m--;
		}
	}
}

/****************************************\
函数功能：从n个数中随机选择m个不同的数
函数输入：n为样本空间，m为选择的个数
函数输出：在屏幕上打印选取的数
算法描述：结果范围在[0,n),思想简单：每生成
		一个随机数就检查是否与已存在的数重合
\****************************************/
void random2(int n,int m)
{
	int *a = new int[m];
	srand(time(NULL));//使用这个就可以每次运行不同

	a[0]=rand()%n;
	int temp=0;
	int j=0;
	bool flag=true;
	for(int i=1;i<m;i++)
	{
		temp=rand()%n;
		flag=true;
		for(j=0;j<i;j++)//循环遍历是否有重复的数
		{
			if(temp==a[j])
			{
				i--;
				flag=false;
				break;//其实这里可以用goto语句，但是goto语句不推荐使用
			}
		}
		if(j==i&&flag)
			a[i]=temp;

	}

	for(int k=0;k<m;k++)
		cout<<a[k]<<" ";
}

/****************************************\
函数功能：从n个数中随机选择m个不同的数
函数输入：n为样本空间，m为选择的个数
函数输出：在屏幕上打印选取的数
算法描述：结果范围在[0,n)，从已存在的数组
	      a中选择，当n比较大时，占用空间大
\****************************************/
void random3(int n,int m)  
{  
    int i;  
	srand(time(NULL));//使用这个就可以每次运行不同
    int *a=new int[n];  
    for(i=0;i<n;i++)  
        a[i]=i;  
    for(i=0;i<m;i++)  
    {  
        int j=i+rand()%(n-i); //随机产生 [i,n-1) 的数作为数组的下标  
        if(i!=j)  
        {  
            int temp=a[i];//将a[i]与a[j]互换  
            a[i]=a[j];  
            a[j]=temp;  
		//	swap(a[i],a[j]);//上面三行的互换可以调用库函数
        }  
    }  
   // sort(&a[0],&a[m]); //进行排序
    for(i=0;i<m;i++)  
         cout<<a[i]<<" ";  
}  

/****************************************\
函数功能：从n个数中随机选择m个不同的数
函数输入：n为样本空间，m为选择的个数
函数输出：在屏幕上打印选取的数
算法描述：结果范围在[0,n),利用set中
		  没有重复元素的特性
\****************************************/
void random4(int n,int m)  
{  
    set<int> s; //利用set中没有重复元素的特性
	srand(time(NULL));//使用这个就可以每次运行不同
    while(s.size()<m)  
        s.insert(rand()%n); //若是重复元素则不插入 

    for(set<int>::iterator iter=s.begin();iter!=s.end();iter++)  
        cout<<*iter<<" ";  
}  


void main()
{
	cout<<RAND_MAX<<endl;//随机数的最大范围32767
	//random1(6,4);
	//random2(6,4);
	//random3(6,4);
	random4(6,4);
}